import java.util.Arrays;

public class J092001 {
    public static void bubbleSort(int[] nums){
        int k = nums.length;
        boolean flage = true;
        for(int i = 0;i < k - 1;i++){
            for(int j = 0;j < k - 1- i;j++){
                if(nums[j] > nums[j + 1]){
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flage = false;
                }
            }
            if(flage){
                break;
            }
        }
    }
    public static void quickSort(int[] nums){
        int len = nums.length;
        quickSortInternal(nums,0,len-1);
    }
    public static void quickSortInternal(int[] nums,int left,int right){
        if(left >= right){
            return;
        }
        int base = divide(nums,left,right);
        quickSortInternal(nums,left,base - 1);
        quickSortInternal(nums,base + 1,right);
    }
    public static int divide(int[] nums,int left,int right){
        int base = nums[left];
        int left1 = left;
        while(left < right){
            while(nums[right] >= base && right > left){
                right--;
            }
            while(nums[left] <= base && left < right){
                left++;
            }
            if(left < right){
                exchange(nums,left,right);
            }
        }
        exchange(nums,left,left1);
        return left;
    }
    public static void exchange(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{11,2,13,4,15,6,16,7,18,9,1,12,2,13,3,14,4,15,5,16,6,17,7,18,8,19};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
